Search results for "Brute-force search"

Combining GPU and FPGA technology for efficient exhaustive interaction analysis in GWAS

2016

Interaction between genes has become a major topic in quantitative genetics. It is believed that these interactions play a significant role in genetic variations causing complex diseases. Due to the number of tests required for an exhaustive search in genome-wide association studies (GWAS), a large amount of computational power is required. In this paper, we present a hybrid architecture consisting of tightly interconnected CPUs, GPUs and FPGAs and a fine-tuned software suite to outperform other implementations in pairwise interaction analysis while consuming less than 300Watts and fitting into a standard desktop computer case.

orthoFind Facilitates the Discovery of Homologous and Orthologous Proteins

2015

Finding homologous and orthologous protein sequences is often the first step in evolutionary studies, annotation projects, and experiments of functional complementation. Despite all currently available computational tools, there is a requirement for easy-to-use tools that provide functional information. Here, a new web application called orthoFind is presented, which allows a quick search for homologous and orthologous proteins given one or more query sequences, allowing a recurrent and exhaustive search against reference proteomes, and being able to include user databases. It addresses the protein multidomain problem, searching for homologs with the same domain architecture, and gives a si…

Adjacent vertices can be hard to find by quantum walks

2018

Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs Ω(N) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of two or more adjace…

Adjacent Vertices Can Be Hard to Find by Quantum Walks

2017

Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element only. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs \(\varOmega (N)\) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of …

High-speed exhaustive 3-locus interaction epistasis analysis on FPGAs

2015

Abstract Epistasis, the interaction between genes, has become a major topic in molecular and quantitative genetics. It is believed that these interactions play a significant role in genetic variations causing complex diseases. Several algorithms have been employed to detect pairwise interactions in genome-wide association studies (GWAS) but revealing higher order interactions remains a computationally challenging task. State of the art tools are not able to perform exhaustive search for all three-locus interactions in reasonable time even for relatively small input datasets. In this paper we present how a hardware-assisted design can solve this problem and provide fast, efficient and exhaus…

Towards efficient inductive synthesis from input/output examples

1994

Towards efficient inductive synthesis of expressions from input/output examples

1993

Our goal through several years has been the development of efficient search algorithm for inductive inference of expressions using only input/output examples. The idea is to avoid exhaustive search by means of taking full advantage of semantic equality of many considered expressions. This might be the way that people avoid too big search when finding proof strategies for theorems, etc. As a formal model for the development of the method we use arithmetic expressions over the domain of natural numbers. A new approach for using weights associated with the functional symbols for restricting search space is considered. This allows adding constraints like the frequency of particular symbols in t…

Resource allocation for OFDMA systems with multi-cell joint transmission

2012

This paper considers the downlink resource allocation of a coordinated multi-cell cluster in OFDMA systems with universal frequency reuse. Multi-cell joint transmission is considered via zero-forcing precoding. Furthermore, joint optimization of the user selection and power allocation across multiple subchannels and multiple cells is studied. The objective is to maximize the weighted sum rate under per-base-station power constraints. Based on general duality theory, two iterative resource allocation algorithms are proposed and compared with the optimal solution, which requires an exhaustive search of all possible combinations of users over all subchannels. Simulation results show that the t…

Combined K-Best sphere decoder based on the channel matrix condition number

2008

It is known that sphere decoding (SD) methods can provide maximum-likelihood (ML) detection over Gaussian MIMO channels with lower complexity than the exhaustive search. Channel matrix condition number represents an important influence on the performance of usual detectors. Throughout this paper, two particular cases of a SD method called K-Best carry out a combined detection in order to reduce the computational complexity with predictable performance degradation. Algorithm selection is based on channel matrix condition number thresholding. K-Best is a suboptimal SD algorithm for finding the ML solution of a detection problem. It is based on a fixed complexity tree search, set by a paramete…

Genetic Algorithms Applied to the Design of 3D Photonic Crystals

2011

We aim at determining the optimal configuration of photonic crystal structures capable of carrying out a certain optical task. An exhaustive search would require a high computational cost, in this work we show how genetic algorithms can be applied to reliably find an optimal topology of threedimensional photonic crystals. The fitness, representing the performance of each potential configuration, is calculated by means of finite element analysis. Different experiments are presented in order to illustrate the potential of this 3D design approach.